package 滑动窗口;

import java.util.*;

/**
 * @author tmh
 * @date 2025/3/7 17:58
 * @description
 */
public class T438找到字符串中所有字母异位词 {
    public static void main(String[] args) {
        List<Integer> anagrams = findAnagrams("cbaebabacd", "abc");
        System.out.println(anagrams.size());
    }
    public static List<Integer> findAnagrams(String s, String p) {
        int left = 0, right = 0;
        int valid = 0;
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        //初始化need
        for (char c : p.toCharArray()) {
            int count = need.getOrDefault(c, 0) + 1;
            need.put(c, count);
        }
        while (right < s.length()) {
            //保存当前字符
            char c = s.charAt(right);
            //扩大窗口
            right++;
            //更新窗口内的数据
            if (need.containsKey(c)) {
                //把c放在窗口里面
                window.put(c, window.getOrDefault(c, 0) + 1);
                //更新valid
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            //while这里是，有些情况需要循环更新left
            while (right - left >= p.length()) {
                //保存数据
                if (valid == need.size()) {
                    list.add(left);
                }
                //缩小窗口
                char d = s.charAt(left);
                left++;
                //减少窗口大小
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    //更新窗口中的数据
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return list;
    }
}
